package merge_sort;

public class reversePairs_hard {
    int ret;
    int[] tem;
    public int reversePairs(int[] record) {
        ret = 0;
        tem = new int[record.length];
        mergeSort(record,0,record.length-1);
        return ret;
    }
    public void mergeSort(int[] nums,int left,int right) {
        if(left >= right) return;
        //确定中间点，将数组分为左右两部分[left,mid][mid+1,right]
        int mid = (left+right)/2;
        //对左右两部分分别进行排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //升序排列两个数组,同时计算逆序对数量
        int cur1 = left,cur2=mid+1,i=0;
        while(cur1<=mid && cur2<=right){
            if(nums[cur1] <= nums[cur2]) {
                tem[i++] = nums[cur1++];
            }else {//cur1 所在的数比 cur2 大，更新ret
                ret += mid-cur1+1;
                tem[i++] = nums[cur2++];
            }
        }
        //处理余下单个数组
        while(cur1<=mid) tem[i++]=nums[cur1++];
        while(cur2<=right) tem[i++]=nums[cur2++];
        //更新原数组
        for(i=left;i<=right;i++){
            nums[i] = tem[i-left];
        }

    }
}
